package com.myown.structure.impl;

import com.myown.structure.Queue;
import com.myown.structure.Tree;
import com.myown.structure.TreeNode;

import java.io.Serializable;
import java.util.Iterator;

/**
 * 树抽象类 <p>
 *
 * @author lincky
 * @version v1.0.0
 * @time 2017.02.27 16:35
 */
public abstract class AbstactTree<E extends Comparable<E>>
        implements Tree<E>, Serializable {

    /**
     * 树根 <p>
     */
    transient TreeNode<E> root;

    /**
     * 节点大小 <p>
     */
    transient int size;

    @Override
    public int size() {
        return size;
    }

    @Override
    public E minimun() {
        return minimun(root).item();
    }

    @Override
    public E maximun() {
        return maximun(root).item();
    }

    @Override
    public void insert(E item) {
        insert(root, item);
    }

    @Override
    public void delete(E item) {
        delete(find(item));
    }

    @Override
    public void clear() {
        clear(root);
        size = 0;
    }

    @Override
    public void valid() {
        valid(root);
    }

    @Override
    public Iterator<E> iterator() {
        return new TreeIterator();
    }

    /**
     * 插入节点（O(depth)） <p>
     *
     * @param node 开始节点
     * @param item 元素
     */
    abstract void insert(TreeNode<E> node, E item);

    /**
     * 删除节点（O(depth)） <p>
     *
     * @param node 待删除节点
     */
    abstract void delete(TreeNode<E> node);

    /**
     * test：检验是否为合法二叉树
     */
    abstract void valid(TreeNode<E> node);

    /**
     * 插入节点 <p>
     *
     * 树结构调整原理： <p>
     * 1.树空：插入根节点 <p>
     * 2.由树根向下遍历： <p>
     *     a.插入元素小于父亲元素：左子树为空则插入左子树，不为空遍历左子树 <p>
     *     b.插入元素大于父亲元素：右子树为空则插入右子树，不为空遍历右子树 <p>
     *     c.插入元素等于父亲元素：return <p>
     *
     * @param node 插入节点的父节点
     * @param newNode 插入节点
     * @return <tt>false</tt> - 树中已存在该元素
     */
    boolean singleInsert(TreeNode<E> node, TreeNode<E> newNode) {
        if (root == null) {
            root = newNode;
            size = 1;
            return true;
        }
        TreeNode<E> parent;
        while (node != null) {
            parent = node;
            int cmp = node.item().compareTo(newNode.item());
            // 左树右树
            if (cmp > 0) {
                if ((node = node.left()) == null) {
                    parent.insertLeft(newNode);
                }
            } else if (cmp < 0){
                if ((node = node.right()) == null) {
                    parent.insertRight(newNode);
                }
            } else {
                return false;
            }
        }
        size++;
        return true;
    }

    /**
     * 删除节点 <p>
     *
     * 树结构调整原理：<p>
     * 1.节点没有左孩子：删除位置由右孩子取代（没右孩子则直接删除节点） <p>
     * 2.节点没有右孩子：删除位置由左孩子取代 <p>
     * 3.节点有两个孩子：删除位置由节点后继取代 <p>
     *
     * @param node 待删除节点
     * @return 取代节点
     */
    TreeNode<E> singleDelete(TreeNode<E> node) {
        assert node != null;
        TreeNode<E> replacement;
        // 1.有一个或者没有孩子
        // 2.有两个孩子...
        if (node.left() == null) {
            transplant(node, node.right());
            replacement = node.right();
        } else if (node.right() == null) {
            transplant(node, node.left());
            replacement = node.left();
        } else {
            // 节点右孩子的后继
            TreeNode<E> successor = inOrderSuccessor(node);
            replacement = successor.right();
            // 2.1.节点右孩子的后继不是该节点
            if (successor.parent() != node) {
                transplant(successor, successor.right());
                successor.setRight(node.right());
                successor.right().setParent(successor);
            } else {
                replacement.setParent(successor);
            }
            transplant(node, successor);
            successor.setLeft(node.left());
            successor.left().setParent(successor);
        }
        size--;
        node.clear();
        return replacement;
    }

    /**
     * 将<tt>nodeB</tt>替换<tt>nodeA</tt> <p>
     *
     * 替换原理： <p>
     * 1.若<tt>nodeA</tt>为根节点：直接替换 <p>
     * 2.若<tt>nodeA</tt>为左孩子：将其左孩子替换 <p>
     * 3.若<tt>nodeA</tt>为右孩子：将其右孩子替换 <p>
     *
     * 注：若<tt>nodeB</tt>为空，相当于移除<tt>nodeA</tt> <p>
     *
     * @param nodeA 待替换节点
     * @param nodeB 替换节点
     */
    void transplant(TreeNode<E> nodeA, TreeNode<E> nodeB) {
        assert nodeA != null;
        if (nodeA.parent() == null) {
            root = nodeB;
        } else if (nodeA.isLeft()) {
            nodeA.parent().setLeft(nodeB);
        } else {
            nodeA.parent().setRight(nodeB);
        }
        if (nodeB != null) {
            nodeB.setParent(nodeA.parent());
        }
    }

    /**
     * 从<tt>root</tt>向下寻找元素为<tt>item</tt>的节点 <p>
     *
     * @param item 元素
     * @return 从<tt>root</tt>处寻找元素为<tt>item</tt>的节点
     */
    public TreeNode<E> find(E item) {
        return find(root, item);
    }

    /**
     * 从<tt>node</tt>向下寻找元素为<tt>item</tt>的节点 <p>
     *
     * @param node 开始节点
     * @param item 元素
     * @return 从<tt>node</tt>处寻找元素为<tt>item</tt>的节点
     */
    public TreeNode<E> find(TreeNode<E> node, E item) {
        if (item == null) {
            return null;
        }
        while (node != null && !node.item().equals(item)) {
            if (item.compareTo(node.item()) < 0) {
                node = node.left();
            } else {
                node = node.right();
            }
        }
        return node;
    }

    /**
     * 从<tt>node</tt>向下寻找最小元素节点 <p>
     *
     * @param node 开始节点
     * @see #maximun(TreeNode)
     * @return 从<tt>node</tt>向下最小的元素节点
     */
    public TreeNode<E> minimun(TreeNode<E> node) {
        while (node.left() != null) {
            node = node.left();
        }
        return node;
    }

    /**
     * 从<tt>node</tt>向下寻找最大元素节点 <p>
     *
     * @param node 开始节点
     * @see #minimun(TreeNode)
     * @return 从<tt>node</tt>向下最大的元素节点
     */
    public TreeNode<E> maximun(TreeNode<E> node) {
        while (node.right() != null) {
            node = node.right();
        }
        return node;
    }

    /**
     * 节点<tt>node</tt>的中序后继 <p>
     *
     * <tt>node</tt>的中序后继是一个值大于node元素且为其中最小元素的节点 <p>
     *
     * @param node 节点
     * @see #inOrderPredecessor(TreeNode)
     * @return node的中序后继
     */
    public TreeNode<E> inOrderSuccessor(TreeNode<E> node) {
        assert node != null;
        // 右子树非空
        if (node.right() != null) {
            return minimun(node.right());
        }
        // 若node的右子树为空，且node有一个中序后继
        // 那么这个中序后继一定是node的最底层祖先，并且左孩子也是node的祖先
        TreeNode<E> parent = node.parent();
        while (parent != null && node == parent.right()) {
            node = parent;
            parent = parent.parent();
        }
        return parent;
    }

    /**
     * 节点<tt>node</tt>的中序前驱 <p>
     *
     * <tt>node</tt>的中序前驱是一个值小于node元素且为其中最大元素的节点 <p>
     *
     * @param node 节点
     * @see #inOrderSuccessor(TreeNode)
     * @return node的中序前驱
     */
    TreeNode<E> inOrderPredecessor(TreeNode<E> node) {
        assert node != null;
        // 左子树非空
        if (node.left() != null) {
            return maximun(node.left());
        }
        // 若node的右子树为空，且node有一个中序前驱
        // 那么这个中序后继一定是node的最底层祖先，并且右孩子也是node的祖先
        TreeNode<E> parent = node.parent();
        while (parent != null && node == parent.left()) {
            node = parent;
            parent = parent.parent();
        }
        return parent;
    }


    /**
     * 左旋 <p>
     *
     * 旋转原理：<p>
     * 将其右孩子替换该节点，其右孩子的左孩子成为成为节点的右
     * 孩子，并让节点成为替换节点的左孩子 <p>
     *
     * @param node 节点
     * @see #rightRotate(TreeNode)
     */
    void leftRotate(TreeNode<E> node) {
        /*
         *            A(-2)                   B(1)
         *              \        左旋转       /   \
         *             B(0)     ---->       A(0)   \
         *             /   \                   \    \
         *           BL(0)  BR(0)              BL(0) BR(0)
         *  旋转之后树的深度之差不超过1
         */
        assert node != null;
        TreeNode<E> right = node.right();
        // 将节点的右子树的左子树插入节点右子树
        node.setRight(right.left());
        if (right.left() != null) {
            right.left().setParent(node);
        }
        transplant(node, right);
        right.setLeft(node);
        node.setParent(right);
    }

    /**
     * 右旋 <p>
     *
     * 旋转原理：<p>
     * 将其左孩子替换该节点，其左孩子的右孩子成为成为节点的左孩子，并让节点成为替换节点的右孩子 <p>
     *
     * @param node 节点
     * @see #leftRotate(TreeNode)
     */
    void rightRotate(TreeNode<E> node){
        /*
         *             A(2)                     B(-1)
         *            /         右旋转          /    \
         *          B(0)       ------>         /     A(0)
         *         /   \                      /      /
         *       BL(0) BR(0)                BL(0)  BR(0)
         */
        assert node != null;
        TreeNode<E> left = node.left();
        // 将节点的右子树的左子树插入节点右子树
        node.setLeft(left.right());
        if (left.right() != null) {
            left.right().setParent(node);
        }
        transplant(node, left);
        left.setRight(node);
        node.setParent(left);
    }

    private void clear(TreeNode<E> node) {
        if (node != null) {
            clear(node.left());
            clear(node.right());
            node.clear();
        }
    }

    /**
     * 树迭代器 <p>
     *
     * 迭代原理：树的中序遍历 <p>
     */
    private class TreeIterator implements Iterator<E> {
        TreeNode<E> next;

        TreeIterator() {
            next = minimun(root);
        }

        @Override
        public boolean hasNext() {
            return next != null;
        }

        @Override
        public E next() {
            E item = next.item();
            next = inOrderSuccessor(next);
            return item;
        }

    }

    /**
     * 树内部链接节点 <p>
     *
     * 节点结构：左孩子，右孩子，父亲节点，元素 <p>
     *
     * @param <E> 存储数据类型
     */
    abstract static class Node<E extends Comparable<E>> implements TreeNode<E> {
        E item;
        TreeNode<E> left;
        TreeNode<E> right;
        TreeNode<E> parent;

        public Node() {
        }

        Node(E item) {
            this.item = item;
        }

        @Override
        public boolean isLeft() {
            return this == parent.left();
        }

        @Override
        public boolean isRight() {
            return this == parent.right();
        }

        @Override
        public TreeNode<E> left() {
            return left;
        }

        @Override
        public TreeNode<E> right() {
            return right;
        }

        @Override
        public TreeNode<E> parent() {
            return parent;
        }

        @Override
        public void setLeft(TreeNode<E> left) {
            this.left = left;
        }

        @Override
        public void setRight(TreeNode<E> right) {
            this.right = right;
        }

        @Override
        public void setParent(TreeNode<E> parent) {
            this.parent = parent;
        }

        @Override
        public E item() {
            return item;
        }

        @Override
        public void clear() {
            item = null;
            left = null;
            right = null;
            parent = null;
        }

        @Override
        public void insertLeft(TreeNode<E> left) {
            setLeft(left);
            left.setParent(this);
        }

        @Override
        public void insertRight(TreeNode<E> right) {
            setRight(right);
            right.setParent(this);
        }

        @Override
        public String toString() {
            return "Node{" +
                    "item=" + item +
                    '}';
        }
    }



}
